import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class LeetCode313 {

    public static void main(String[] args) {
        int n = 12;
        int[] primes = {2, 7, 13, 19};

        System.out.println(nthSuperUglyNumber(n, primes));
    }

    public static int nthSuperUglyNumber(int n, int[] primes) {
        int m = primes.length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < m; i++) {
            queue.add(new int[]{primes[i], i, 0});
        }
        int[] ans = new int[n];
        ans[0] = 1;
        for (int i = 1; i < n; ) {
            int[] poll = queue.poll();
            int val = poll[0];
            int j = poll[1];
            int idx = poll[2];
            if (val != ans[i - 1]) {
                ans[i++] = val;
            }
            queue.add(new int[]{ans[idx + 1] * primes[j], j, idx + 1});
        }
        return ans[n - 1];
    }

    public static int nthSuperUglyNumber1(int n, int[] primes) {
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.add(1L);
        set.add(1L);
        while (n-- > 0) {
            long x = queue.poll();
            if (n == 0) {
                return (int) x;
            }
            for (int k : primes) {
                if (!set.contains(k * x)) {
                    queue.add(k * x);
                    set.add(k * x);
                }
            }
        }
        return -1; // never
    }
}
